class Solution {
    List<List<Integer>> lists = new ArrayList<List<Integer>>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        if(n < k) {
            return lists;
        }
        if(n == k) {
            int a = 1;
            while(a <= n) {
                list.add(a);
                a++;
            }
            lists.add(new ArrayList<Integer>(list));
            return lists;
        }
        dfc(1,n,k);
        return lists;
    }

    public void dfc(int cur,int n,int k) {
        // 剪枝：list 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 list
        if (list.size() + (n - cur + 1) < k) {
            return;
        }
        // 记录合法的答案
        if (list.size() == k) {
            lists.add(new ArrayList<Integer>(list));
            return;
        }
        // 考虑选择当前位置
        list.add(cur);
        dfc(cur + 1, n, k);
        list.remove(list.size() - 1);
        // 考虑不选择当前位置
        dfc(cur + 1, n, k);
    }
}